package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-03-21 20:36
 */
public class QLint80 {
    public int median(int[] nums) {
        int n = nums.length;
        int res;
        if((n & 1) == 1) {
            res = select(nums, 0, n - 1, n / 2);
        } else {
            res = select(nums, 0, n - 1, n / 2 - 1);
        }

        return res;
    }

    private int select(int[] nums, int start, int end, int k) {
        if(start >= end) {
            return nums[k];
        }

        int i = start, j = end;
        int povit = nums[(i + j) / 2];

        while(i <= j) {
            while(i <= j && nums[i] < povit) {
                i++;
            }

            while(i <= j && nums[j] > povit) {
                j--;
            }

            if(i <= j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;

                i++;
                j--;
            }
        }


        if(k <= j) {
            return select(nums, start, j, k);
        }

        if(k >= i) {
            return select(nums, i, end, k);
        }

        return nums[k];
    }
}
